package ink.lovejinhu.swardToOffer;

/**
 * @Author: jin
 * @Date: 2021/8/24 22:25
 * @Version: V1.0
 * @Slogan: Great people are not born great, but show their greatness in the process of growing up
 **/
public class Offer_040 {
    public int[] getLeastNumbers(int[] arr, int k) {
        this.quickSort(arr, 0, arr.length - 1);
        int[] ints = new int[k];
        for (int i = 0; i < k; i++) {
            ints[i] = arr[i];
        }
        return ints;
    }

    /**
     * 板子题，6分钟可写出来
     *
     * @param arr
     * @param left
     * @param right
     */
    public void quickSort(int arr[], int left, int right) {
        if (left >= right) return;
        int leftTemp = left - 1;
        int righTemp = right + 1;
        int mid = arr[leftTemp + righTemp >> 1];
        while (leftTemp < righTemp) {
            do {
                leftTemp++;
            } while (arr[leftTemp] < mid);
            do {
                righTemp--;
            } while (arr[righTemp] > mid);
            if (leftTemp < righTemp) {
                swap(arr, leftTemp, righTemp);
            }
        }
        quickSort(arr, left, leftTemp - 1);
        quickSort(arr, righTemp + 1, right);
    }

    public void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}
